package baseclass.j_dp.dp.oneZeroBag;

import java.util.Arrays;

/**
 * 给定两个数组w和v， 两个数组长度相等， w[i]表示第i件商品的重量， v[i]表示第i件商品的价值。
 * 再给定一个整数bag， 要求你挑选商品的重量加起来一定不能超过bag，
 * 返回满足这个条件下， 你能获得的最大价值。
 *
 * @date 2020/3/2 12:19
 */
public class Code01_01Bag {
    public static int maxValue1(int[] W, int[] V, int i, int alreadyWeight, int bag) {
        if (alreadyWeight > bag) return Integer.MIN_VALUE;
        if (i >= W.length) {
            return 0;
        }
        return Math.max(
                maxValue1(W, V, i + 1, alreadyWeight, bag),
                maxValue1(W, V, i + 1, alreadyWeight + W[i], bag) + V[i]
        );
    }

    /**
     * 方式2：带有记忆性回溯。memo[i][j]表示来到i位置当前背包容量为j时，
     * 所能获得的最大利润。
     */
    public static int maxValue2(int[] W, int[] V, int bag) {
        int[][] memo = new int[W.length][bag + 1];
        for (int i = 0; i < W.length; i++) {
            Arrays.fill(memo[i], -1);
        }
        return process(W, V, 0, 0, bag, memo);
    }

    private static int process(int[] W, int[] V, int i, int alreadyWeight, int bag, int[][] memo) {
        if (alreadyWeight > bag) return Integer.MIN_VALUE;
        if (i >= W.length) {
            return 0;
        }
        if (memo[i][alreadyWeight] != -1) return memo[i][alreadyWeight];
        return memo[i][alreadyWeight] =
                Math.max(
                        process(W, V, i + 1, alreadyWeight, bag, memo),
                        process(W, V, i + 1, alreadyWeight + W[i], bag, memo) + V[i]
                );
    }

    /**
     * 方式3：DP1
     */
    public static int maxValue3(int[] W, int[] V, int bag) {
        int[][] dp = new int[W.length + 1][bag + 1];
        //初始化最后一列为0，默认就是0
        for (int i = W.length - 1; i >= 0; i--) {
            for (int j = 0; j <= bag; j++) {
                //i物品不要
                dp[i][j] = dp[i + 1][j];
                //第i件物品要
                if (j + W[i] <= bag) {
                    dp[i][j] = Math.max(dp[i][j], V[i] + dp[i + 1][j + W[i]]);
                }
            }
        }
        return dp[0][0];
    }

    /**
     * DP1优化空间。O(2n)
     */
    public static int maxValue4(int[] W, int[] V, int bag) {
        int[][] dp = new int[2][bag + 1];
        int temp = 0;
        Arrays.fill(dp[temp], 0);
        //初始化最后一列为0，默认就是0
        for (int i = W.length - 1; i >= 0; i--) {
            for (int j = 0; j <= bag; j++) {
                //i物品不要
                dp[1 - temp][j] = dp[temp][j];
                //第i件物品要
                if (j + W[i] <= bag) {
                    dp[1 - temp][j] = Math.max(dp[1 - temp][j], V[i] + dp[temp][j + W[i]]);
                }
            }
            temp = 1 - temp;// 0 - 1 - 0 - 1
        }
        return dp[temp][0];
    }


    public static void main(String[] args) {
        int[] weight = {3, 2, 4, 7};
        int[] value = {5, 6, 3, 19};
        int bag = 12;
        System.out.println(maxValue1(weight, value, 0, 0, bag));
        System.out.println(maxValue2(weight, value, bag));
        System.out.println(maxValue3(weight, value, bag));
        System.out.println(maxValue4(weight, value, bag));
    }
}
